//给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。 
//
// 如果树中有不止一个众数，可以按 任意顺序 返回。 
//
// 假定 BST 满足如下定义： 
//
// 
// 结点左子树中所含节点的值 小于等于 当前节点的值 
// 结点右子树中所含节点的值 大于等于 当前节点的值 
// 左子树和右子树都是二叉搜索树 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,null,2,2]
//输出：[2]
// 
//
// 示例 2： 
//
// 
//输入：root = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [1, 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内） 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 440 👎 0

package leetcode.editor.cn;

import java.util.*;

class FindModeInBinarySearchTree {
    public static void main(String[] args) {
        Solution solution = new FindModeInBinarySearchTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        /**
         * 暴力法（遍历成数组即可）
         *
         * @param root
         * @return
         */
//        public int[] findMode(TreeNode root) {
//            traversal(root);
//            for (int i = 0; i < res.size(); i++) {
//                map.put(res.get(i), map.getOrDefault(res.get(i), 0) + 1);
//            }
//
//            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//                if (entry.getValue() >= max) {
//                    max = entry.getValue();
//                }
//            }
//
//            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//                if (entry.getValue() == max) {
//                    temp.add(entry.getKey());
//                }
//            }
//
//            int[] ints = new int[temp.size()];
//            for (int i = 0; i < temp.size(); i++) {
//                ints[i] = temp.get(i);
//            }
//            return ints;
//        }
//
//        int max = Integer.MIN_VALUE;
//        Map<Integer, Integer> map = new HashMap<>();
//        List<Integer> res = new ArrayList<>();
//        List<Integer> temp = new ArrayList<>();
//
//        public TreeNode traversal(TreeNode root) {
//            if (root == null) {
//                return null;
//            }
//
//            if (root.left != null) traversal(root.left);
//            res.add(root.val);
//            if (root.right != null) traversal(root.right);
//
//            return root;
//        }

        /**
         * 递归法（根据二叉树的性质）
         *
         * @param root
         * @return
         */
//        public int[] findMode(TreeNode root) {
//            searchBST(root);
//            int[] ints = new int[res.size()];
//            for (int i = 0; i < res.size(); i++) {
//                ints[i] = res.get(i);
//            }
//            return ints;
//        }
//
//        TreeNode pre;
//        int maxCount; // 最大频率
//        int count; // 统计频率
//        List<Integer> res = new ArrayList<>();
//
//        public TreeNode searchBST(TreeNode root) {
//            if (root == null) {
//                return null;
//            }
//
//            searchBST(root.left);   // 左
//
//            if (pre == null) {
//                count = 1;  // 第一个节点
//            } else if (pre.val == root.val) {
//                count++;    // 当当前节点和上一个节点相同，频率加一
//            } else {
//                count = 1;  // 此时不相同，重新统计
//            }
//            pre = root;   // 移动到下一个节点
//
//            if (count == maxCount) {   // 此时频率等于最大频率
//                res.add(root.val);
//            }
//            if (count > maxCount) {
//                maxCount = count;
//                res.clear();    // 此时最大的频率改变，要清空集合里的所有元素
//                res.add(root.val);// 重新赋值
//            }
//
//            searchBST(root.right);  //右
//
//            return root;
//        }
//    }

        TreeNode pre;
        TreeNode cur;
        int maxCount; // 最大频率
        int count; // 统计频率
        List<Integer> res = new ArrayList<>();

        /**
         * 迭代法（中序遍历）
         *
         * @param root
         * @return
         */
        public int[] findMode(TreeNode root) {
            Stack<TreeNode> stack = new Stack();
            cur = root;
            pre = null;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    if (pre == null) {
                        count = 1;
                    } else if (pre.val == cur.val) {
                        count++;
                    } else {
                        count = 1;

                    }

                    if (count == maxCount) {
                        res.add(cur.val);
                    }

                    if (count > maxCount) {
                        maxCount = count;
                        res.clear();
                        res.add(cur.val);
                    }
                    pre = cur;  // 移动节点
                    cur = cur.right;  // 遍历右边
                }
            }

            int[] ints = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                ints[i] = res.get(i);
            }

            return ints;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
